home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / tex / lgrind.zoo / regexp.c < prev    next >
C/C++ Source or Header  |  1992-09-28  |  15KB  |  682 lines
  1. #ifndef lint
  2. static char *sccsid="@(#)regexp.c    1.2 (LBL) 4/12/85";
  3. static char Version[] =
  4.    "$Id: regexp.c,v 1.2 91/10/01 00:30:20 gvr Exp $";
  5. #endif
  6.  
  7. /*
  8.  * Regular expression matching routines for lgrind/tgrind/tfontedpr.
  9.  *
  10.  * These routines were written by Dave Presotto (I think) for vgrind.
  11.  * Minor mods & attempts to improve performance by Van Jacobson
  12.  * (van@@lbl-rtsg) and Chris Torek (chris@@maryland).
  13.  *
  14.  * Modifications.
  15.  * --------------
  16.  *    Sep 91    George V Reilly    Fixed up some bogus uses of @NIL@ and @NULL@.
  17.  * 30 Mar 85    Van & Chris    Changed @expmatch()@ to return pointer to
  18.  *                start of what was matched in addition to
  19.  *                pointer to match end.  Several changes to
  20.  *                improve performance (too numerous to mention).
  21.  * 11 Dec 84    Dave Presotto    Written.
  22.  */
  23.  
  24.  
  25. #include <stdio.h>
  26. #include <malloc.h>
  27. #include <ctype.h>
  28.  
  29. typedef int    boolean;
  30. #define TRUE    1
  31. #define FALSE    0
  32.  
  33. #define makelower(c) (isupper((c)) ? tolower((c)) : (c))
  34.  
  35. void    expconv();     /* forward declaration */
  36.  
  37. int    (*re_strncmp)();     /* function used by @expmatch()@ to compare
  38.               * strings.  The caller should make it point to
  39.               * @strncmp()@ if case is significant &
  40.               * @lc_strncmp()@ otherwise.
  41.               */
  42.  
  43.  
  44. /*  @lc_strncmp()@ ---    like @strncmp()@ except that we convert the
  45.  *            first string to lower case before comparing.
  46.  */
  47.    int
  48. lc_strncmp(s1, s2, len)
  49.    register char *s1,*s2;
  50.    register int len;
  51. {
  52.    while (len-- > 0)
  53.       if (*s2 - makelower(*s1))
  54.      return 1;
  55.       else
  56.      s2++, s1++;
  57.    
  58.    return 0;
  59. }
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93. /*  The following routine converts an irregular expression to
  94.  *  internal format.
  95.  *
  96.  *  Either meta symbols (%|\a|%, %|\d|%, or %|\p|%) or character strings
  97.  *  or operations (alternation or parenthesizing) can be specified.
  98.  *  Each starts with a descriptor byte.  The descriptor byte
  99.  *  has @STR@ set for strings, @META@ set for meta symbols,
  100.  *  and @OPER@ set for operations.  The descriptor byte can also have
  101.  *  the @OPT@ bit set if the object defined is optional.  Also @ALT@
  102.  *  can be set to indicate an alternation.
  103.  *
  104.  *  For metasymbols, the byte following the descriptor byte identities
  105.  *  the meta symbol (containing an ASCII @'a'@, @'d'@, @'p'@, @'|'@,
  106.  *  or @'('@).  For strings, the byte after the descriptor is a
  107.  *  character count for the string:
  108.  *@
  109.  *    meta symbols :=    descriptor
  110.  *            symbol
  111.  *
  112.  *    strings :=    descriptor
  113.  *            character count
  114.  *            the string
  115.  *
  116.  *    operations :=    descriptor
  117.  *            symbol
  118.  *            character count@
  119.  */
  120.  
  121.  
  122. /*
  123.  *  handy macros for accessing parts of match blocks
  124.  */
  125. #define MSYM(A)     (*(A+1))    /* symbol in a meta symbol block */
  126. #define MNEXT(A) (A+2)        /* character following a metasymbol block */
  127.  
  128. #define OSYM(A)     (*(A+1))    /* symbol in an operation block */
  129. #define OCNT(A)     (*(A+2))    /* character count */
  130. #define ONEXT(A) (A+3)        /* next character after the operation */
  131. #define OPTR(A)     (A+*(A+2))    /* place pointed to by the operator */
  132.  
  133. #define SCNT(A)     (*(A+1))    /* byte count of a string */
  134. #define SSTR(A)     (A+2)        /* address of the string */
  135. #define SNEXT(A) (A+2+*(A+1))    /* character following the string */
  136.  
  137.  
  138. /*
  139.  *  bit flags in the descriptor 
  140.  */
  141. #define OPT     1
  142. #define STR     2
  143. #define META     4
  144. #define ALT     8
  145. #define OPER    16
  146.  
  147. char *ure;        /* pointer current position in unconverted exp */
  148. char *ccre;        /* pointer to current position in converted exp */
  149.  
  150.  
  151.  
  152. /*
  153.  * Convert an irregular expression to the internal form
  154.  */
  155.    char *
  156. convexp(re)
  157.    char *re;        /* unconverted irregular expression */
  158. {
  159.    register char *cre;    /* pointer to converted regular expression */
  160.    
  161.    /* allocate room for the converted expression */
  162.    if (re == NULL)
  163.       return NULL;
  164.    if (*re == '\0')
  165.       return NULL;
  166.    cre = malloc(4 * strlen(re) + 3);
  167.    ccre = cre;
  168.    ure = re;
  169.    
  170.    /* start the conversion with a %|\a|% */
  171.    *cre = META | OPT;
  172.    MSYM(cre) = 'a';
  173.    ccre = MNEXT(cre);
  174.    
  175.    /* start the conversion (it's recursive) */
  176.    expconv();
  177.    *ccre = 0;
  178.    return cre;
  179. }
  180.  
  181.  
  182. /*
  183.  * Actually do the conversion
  184.  */
  185.    static void
  186. expconv()
  187. {
  188.    register char *cs;    /* pointer to current symbol in converted exp */
  189.    register char c;    /* character being processed */
  190.    register char *acs;    /* pointer to last alternate */
  191.    register int temp;
  192.    
  193.    /* let the conversion begin */
  194.    acs = NULL;
  195.    cs = NULL;
  196.    while (*ure != '\0') {
  197.       switch (c = *ure++) {
  198.      
  199.       case '\\':
  200.      switch (c = *ure++) {
  201.         
  202.         /* escaped characters are just characters */
  203.      default:
  204.         if (cs == NULL || (*cs & STR) == 0) {
  205.            cs = ccre;
  206.            *cs = STR;
  207.            SCNT(cs) = 1;
  208.            ccre += 2;
  209.         } else 
  210.            SCNT(cs)++;
  211.         *ccre++ = c;
  212.         break;
  213.         
  214.         /* normal(?) metacharacters */
  215.      case 'a':
  216.      case 'd':
  217.      case 'e':
  218.      case 'p':
  219.         if (acs != NULL && acs != cs) {
  220.            do {
  221.           temp = OCNT(acs);
  222.           OCNT(acs) = ccre - acs; 
  223.           acs -= temp;
  224.            } while (temp != 0);
  225.            acs = NULL;
  226.         }
  227.         cs = ccre;
  228.         *cs = META;
  229.         MSYM(cs) = c;
  230.         ccre = MNEXT(cs);
  231.         break;
  232.      }
  233.      break;
  234.      
  235.      /* just put the symbol in */
  236.       case '^':
  237.       case '$':
  238.      if (acs != NULL && acs != cs) {
  239.         do {
  240.            temp = OCNT(acs);
  241.            OCNT(acs) = ccre - acs;
  242.            acs -= temp;
  243.         } while (temp != 0);
  244.         acs = NULL;
  245.      }
  246.      cs = ccre;
  247.      *cs = META;
  248.      MSYM(cs) = c;
  249.      ccre = MNEXT(cs);
  250.      break;
  251.      
  252.      /* mark the last match sequence as optional */
  253.       case '?':
  254.      if (cs)
  255.         *cs = *cs | OPT;
  256.      break;
  257.      
  258.      /* recurse and define a subexpression */
  259.       case '(':
  260.      if (acs != NULL && acs != cs) {
  261.         do {
  262.            temp = OCNT(acs);
  263.            OCNT(acs) = ccre - acs;
  264.            acs -= temp;
  265.         } while (temp != 0);
  266.         acs = NULL;
  267.      }
  268.      cs = ccre;
  269.      *cs = OPER;
  270.      OSYM(cs) = '(';
  271.      ccre = ONEXT(cs);
  272.      expconv();
  273.      OCNT(cs) = ccre - cs;        /* offset to next symbol */
  274.      break;
  275.      
  276.      /* return from a recursion */
  277.       case ')':
  278.      if (acs != NULL) {
  279.         do {
  280.            temp = OCNT(acs);
  281.            OCNT(acs) = ccre - acs;
  282.            acs -= temp;
  283.         } while (temp != 0);
  284.         acs = NULL;
  285.      }
  286.      cs = ccre;
  287.      *cs = META;
  288.      MSYM(cs) = c;
  289.      ccre = MNEXT(cs);
  290.      return;
  291.      
  292.      /* Mark the last match sequence as having an alternate. */
  293.      /* The third byte will contain an offset to jump over the */
  294.      /* alternate match in case the first did not fail */
  295.       case '|':
  296.      if (acs != NULL && acs != cs)
  297.         OCNT(ccre) = ccre - acs;    /* make a back pointer */
  298.      else
  299.         OCNT(ccre) = 0;
  300.      *cs |= ALT;
  301.      cs = ccre;
  302.      *cs = OPER;
  303.      OSYM(cs) = '|';
  304.      ccre = ONEXT(cs);
  305.      acs = cs;    /* remember that the pointer is to be filled */
  306.      break;
  307.      
  308.      /* if it's not a metasymbol, just build a character string */
  309.       default:
  310.      if (cs == NULL || (*cs & STR) == 0) {
  311.         cs = ccre;
  312.         *cs = STR;
  313.         SCNT(cs) = 1;
  314.         ccre = SSTR(cs);
  315.      } else
  316.         SCNT(cs)++;
  317.      *ccre++ = c;
  318.      break;
  319.       }
  320.    }
  321.    if (acs != NULL) {
  322.       do {
  323.      temp = OCNT(acs);
  324.      OCNT(acs) = ccre - acs;
  325.      acs -= temp;
  326.       } while (temp != 0);
  327.       acs = NULL;
  328.    }
  329.    return;
  330. } /* end of @expconv()@ */
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345.  
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353.  
  354.  
  355.  
  356.  
  357.  
  358.  
  359.  
  360.  
  361.  
  362.  
  363.  
  364.  
  365. /*
  366.  *  The following routine recognises an irregular expression
  367.  *  with the following special characters:
  368.  *
  369.  *    %|\?|%        means last match was optional
  370.  *    %|\a|%        matches any number of characters
  371.  *    %|\d|%        matches any number of spaces and tabs
  372.  *    %|\p|%        matches any number of alphanumeric characters.
  373.  *            The characters matched will be copied into
  374.  *            the area pointed to by @mstring@.
  375.  *    %|\||%        alternation
  376.  *    %|\( \)|%    grouping used mostly for alternation and
  377.  *            optionality
  378.  *
  379.  *  The irregular expression must be translated to internal form
  380.  *  prior to calling this routine
  381.  *
  382.  *  The value returned is the pointer to the last character matched.
  383.  *  If @strtptr@ is non-@NULL@, a pointer to the start of the string matched
  384.  *  (excluding %|\a|% matches) will be returned at @*strtptr@.  
  385.  *  If @mstring@ is non-@NULL@, the string matched by a %|\p|% will be copied
  386.  *  into @mstring@.
  387.  */
  388.  
  389. boolean _escaped;        /* true if we are currently @_escaped@ */
  390. char *_start;            /* start of string.  Set in @putScp()@. */
  391.  
  392.  
  393.  
  394.    char *
  395. expmatch(s, re, strtptr, mstring)
  396.    register char *s;        /* string to check for a match in */
  397.    register char *re;        /* a conv